package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2021/7/10 12:58
 * @description：https://leetcode-cn.com/problems/time-based-key-value-store/
 */
public class 基于时间的键值存储 {
    @Test
    public void test() {
        //  Solution solution = new Solution();
        TimeMap timeMap = new TimeMap();
        timeMap.set("love","high",20);
        timeMap.set("love","low",10);
        System.out.println(timeMap.get("love",5));
        System.out.println(timeMap.get("love",10));
        System.out.println(timeMap.get("love", 15));
        System.out.println(timeMap.get("love", 20));
        System.out.println(timeMap.get("love",25));
    }


    class TimeMap {

        private Map<String, List<Val>> map;

        /** Initialize your data structure here. */
        public TimeMap() {
            map = new HashMap<>();
        }

        public void set(String key, String value, int timestamp) {
            List<Val> list = map.getOrDefault(key, new ArrayList<>());
            list.add(new Val(value, timestamp));
            Collections.sort(list);
            map.put(key, list);

        }
        public String get(String key, int timestamp) {
            List<Val> list = map.getOrDefault(key, new ArrayList<>());
            if (list.size() == 0) return "";
            int i = binarySearch(list, timestamp);
            System.out.println(list);
            return list.get(i).timestamp <= timestamp ? list.get(i).value : "";

        }
        private int binarySearch(List<Val> list, int timestamp) {
            int l = 0;
            int r = list.size() - 1;
            int mid;
            while(l < r) {
                mid = l + r + 1 >> 1;
                if (list.get(mid).timestamp <= timestamp) {
                    l = mid;
                } else {
                    r = mid - 1;
                }
            }
            return l;
        }
    }

    class Val implements Comparable<Val>{
        public String value;
        public int timestamp;

        public Val(String value, int timestamp) {
            this.value = value;
            this.timestamp = timestamp;
        }

        @Override
        public String toString() {
            return "Val{" +
                    "value='" + value + '\'' +
                    ", timestamp=" + timestamp +
                    '}';
        }

        @Override
        public int compareTo(Val o) {
            if (this.timestamp == o.timestamp) {
                return this.value.compareTo(o.value);
            }
            return this.timestamp - o.timestamp;
        }
    }

/**
 * Your TimeMap object will be instantiated and called as such:
 * TimeMap obj = new TimeMap();
 * obj.set(key,value,timestamp);
 * String param_2 = obj.get(key,timestamp);
 */



}
